{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Non-overlapping Palindrome Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxPalindromes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不重叠回文子字符串的最大数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 和一个 <strong>正</strong> 整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>从字符串 <code>s</code> 中选出一组满足下述条件且 <strong>不重叠</strong> 的子字符串：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个子字符串的长度 <strong>至少</strong> 为 <code>k</code> 。</li>\n",
    "\t<li>每个子字符串是一个 <strong>回文串</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回最优方案中能选择的子字符串的 <strong>最大</strong> 数目。</p>\n",
    "\n",
    "<p><strong>子字符串</strong> 是字符串中一个连续的字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abaccdbbd\", k = 3\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>可以选择 s = \"<em><strong>aba</strong></em>cc<em><strong>dbbd</strong></em>\" 中斜体加粗的子字符串。\"aba\" 和 \"dbbd\" 都是回文，且长度至少为 k = 3 。\n",
    "可以证明，无法选出两个以上的有效子字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"adbcda\", k = 2\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>字符串中不存在长度至少为 2 的回文子字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= s.length &lt;= 2000</code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-non-overlapping-palindrome-substrings](https://leetcode.cn/problems/maximum-number-of-non-overlapping-palindrome-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-non-overlapping-palindrome-substrings](https://leetcode.cn/problems/maximum-number-of-non-overlapping-palindrome-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abaccdbbd\"\\n3', '\"adbcda\"\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        f=[0]*(n+1)\n",
    "        for i in range(2*n-1):\n",
    "            l,r=i//2,i//2+i%2\n",
    "            f[l+1]=max(f[l],f[l+1])\n",
    "            while l>=0 and r<=n-1 and s[l]==s[r]:\n",
    "                if r-l+1>=k:\n",
    "                    f[r+1]=max(f[r+1],f[l]+1)\n",
    "                    break\n",
    "                l-=1\n",
    "                r+=1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        lastl = 0\n",
    "        ret = 0\n",
    "        if k == 1: return len(s)\n",
    "        for i in range(0, len(s)):\n",
    "            find = False\n",
    "            plus = 0\n",
    "            while lastl<=i-plus and i+1+plus<len(s) and s[i-plus] == s[i+1+plus]:\n",
    "                l = i+1+plus - (i-plus) + 1\n",
    "                if l >= k:\n",
    "                    ret += 1\n",
    "                    find = True\n",
    "                    lastl = i+1+plus+1\n",
    "                    break\n",
    "                plus += 1\n",
    "            if find: continue\n",
    "            plus = 0\n",
    "            while lastl<=i-plus and i+plus<len(s) and s[i+plus] == s[i-plus]:\n",
    "                l = i+plus - (i-plus) + 1\n",
    "                if l >= k:\n",
    "                    ret += 1\n",
    "                    lastl = i + plus + 1\n",
    "                    break\n",
    "                plus += 1\n",
    "\n",
    "        ret2 = 0\n",
    "        lastl = 0\n",
    "        s = s[::-1]\n",
    "        for i in range(0, len(s)):\n",
    "            find = False\n",
    "            plus = 0\n",
    "            while lastl<=i-plus and i+1+plus<len(s) and s[i-plus] == s[i+1+plus]:\n",
    "                l = i+1+plus - (i-plus) + 1\n",
    "                if l >= k:\n",
    "                    ret2 += 1\n",
    "                    find = True\n",
    "                    lastl = i+1+plus+1\n",
    "                    break\n",
    "                plus += 1\n",
    "            if find: continue\n",
    "            plus = 0\n",
    "            while lastl<=i-plus and i+plus<len(s) and s[i+plus] == s[i-plus]:\n",
    "                l = i+plus - (i-plus) + 1\n",
    "                if l >= k:\n",
    "                    ret2 += 1\n",
    "                    lastl = i + plus + 1\n",
    "                    break\n",
    "                plus += 1\n",
    "        \n",
    "        return max(ret, ret2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        # 中心扩展 + dp\n",
    "        n = len(s)\n",
    "        f = [0] * (n + 1) # f[i]表示 s[0...i-1]中不重叠回文子字符串的最大数目\n",
    "        for i in range(2 * n - 1):\n",
    "            l, r = i // 2, i // 2 + i % 2 #中心扩展法\n",
    "\n",
    "            f[l + 1] = max(f[l + 1], f[l])\n",
    "            while l >= 0 and r < n and s[l] == s[r]:\n",
    "                if r - l + 1 >= k:\n",
    "                    f[r + 1] = max(f[r + 1], f[l] + 1)\n",
    "                    break\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(2 * n - 1):\n",
    "            l, r = i // 2, i // 2 + i % 2  # 中心扩展法\n",
    "            f[l + 1] = max(f[l + 1], f[l])\n",
    "            while l >= 0 and r < n and s[l] == s[r]:\n",
    "                if r - l + 1 >= k:\n",
    "                    f[r + 1] = max(f[r + 1], f[l] + 1)\n",
    "                    break\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        f=[0]*(n+1)\n",
    "        for i in range(2*n-1):\n",
    "            l,r=i//2,i//2+i%2\n",
    "            f[l+1]=max(f[l],f[l+1])\n",
    "            while l>=0 and r<=n-1 and s[l]==s[r]:\n",
    "                if r-l+1>=k:\n",
    "                    f[r+1]=max(f[r+1],f[l]+1)\n",
    "                    break\n",
    "                l-=1\n",
    "                r+=1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(2 * n - 1):\n",
    "            l = i // 2\n",
    "            r = i // 2 + (i & 1)\n",
    "            f[l + 1] = max(f[l + 1], f[l])\n",
    "            while l >= 0 and r < n and s[l] == s[r]:\n",
    "                if r - l + 1 >= k:\n",
    "                    f[r + 1] = max(f[r + 1], f[l] + 1)\n",
    "                    break\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        if k == 1:\n",
    "            return n\n",
    "\n",
    "        def is_huiwen_ji(index):\n",
    "            cnt = 1\n",
    "            \n",
    "            while index - cnt >= 0 and index + cnt < n:\n",
    "                if s[index-cnt] == s[index+cnt]:\n",
    "                    if cnt * 2 + 1 >= k:\n",
    "                        return index-cnt, index + cnt\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    return -1, -1\n",
    "            return -1, -1\n",
    "\n",
    "        def is_huiwen_ou(index):\n",
    "            if s[index] != s[index-1]:\n",
    "                return -1, -1\n",
    "            cnt = 0\n",
    "            while index - cnt - 1 >= 0 and index + cnt < n:\n",
    "                if s[index-cnt-1] == s[index+cnt]:\n",
    "                    if cnt * 2 + 2 >= k:\n",
    "                        return index-cnt-1, index + cnt\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    return -1, -1\n",
    "            return -1, -1\n",
    "\n",
    "        # print(is_huiwen_ou(7))\n",
    "\n",
    "        res = 0\n",
    "        right = -1\n",
    "        for i in range(1, n):\n",
    "            ji_left, ji_right = is_huiwen_ji(i)\n",
    "            ou_left, ou_right = is_huiwen_ou(i)\n",
    "            cur_min_right = -1\n",
    "            cur_min_left = -1\n",
    "            if ji_right > 0 and ou_right > 0:\n",
    "                if ji_right <= ou_right:\n",
    "                    cur_min_right = ji_right\n",
    "                    cur_min_left = ji_left\n",
    "                else:\n",
    "                    cur_min_right = ou_right\n",
    "                    cur_min_left = ou_left\n",
    "            elif ji_right > 0:\n",
    "                cur_min_right = ji_right\n",
    "                cur_min_left = ji_left\n",
    "            elif ou_right > 0:\n",
    "                cur_min_right = ou_right\n",
    "                cur_min_left = ou_left\n",
    "            else:\n",
    "                continue\n",
    "            \n",
    "            if right == -1:\n",
    "                res += 1\n",
    "                #print(s[cur_min_left:cur_min_right+1])\n",
    "                right = cur_min_right\n",
    "            elif cur_min_right < right:\n",
    "                right = cur_min_left\n",
    "            elif cur_min_left > right:\n",
    "                res += 1\n",
    "                right = cur_min_right\n",
    "                #print(s[cur_min_left:cur_min_right+1])\n",
    "\n",
    "            # print(i, cur_min_left, cur_min_right, right, res)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(2 * n - 1):\n",
    "            l, r = i // 2, i // 2 + i % 2  # 中心扩展法\n",
    "            f[l + 1] = max(f[l + 1], f[l])\n",
    "            while l >= 0 and r < n and s[l] == s[r]:\n",
    "                if r - l + 1 >= k:\n",
    "                    f[r + 1] = max(f[r + 1], f[l] + 1)\n",
    "                    break\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "原问题\n",
    "从长度为j的字符串s中，找到??个回文子串\n",
    "\n",
    "最后一步\n",
    "对于最后一个字符，判断是选还是不选\n",
    "如果不选，直接跳过\n",
    "如果选，找到s[j...i]，满足这是一个回文串\n",
    "这个是关键\n",
    "\n",
    "f[i]表示前i个字符\n",
    "f[i]=f[i-1] f[j]+1\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        f=[0]*(n+1)\n",
    "        '''\n",
    "        试图使用中心扩展法\n",
    "        '''\n",
    "        for i in range(2*n-1):\n",
    "            l=i//2\n",
    "            r=l+i%2\n",
    "            f[l+1]=max(f[l+1],f[l])\n",
    "            while l>=0 and r<n and s[l]==s[r]:\n",
    "                #s[l..r]是一个回文串\n",
    "                if r-l+1>=k:\n",
    "                    f[r+1]=max(f[l]+1,f[r+1])\n",
    "                    break #有贪心的思想\n",
    "                l-=1\n",
    "                r+=1\n",
    "        return f[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(2 * n - 1):\n",
    "            l, r = i // 2, i // 2 + i % 2  # 中心扩展法\n",
    "            f[l + 1] = max(f[l + 1], f[l])\n",
    "            while l >= 0 and r < n and s[l] == s[r]:\n",
    "                if r - l + 1 >= k:\n",
    "                    f[r + 1] = max(f[r + 1], f[l] + 1)\n",
    "                    break\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        return f[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    线性DP\n",
    "    按照回文串的通用解法，进行中心点扩散比较，假设字符串aba，进行中心点扩散的时候需要将字符串假设为a_b_a的\n",
    "    形式，枚举扩散之后的字符串，然后反推对应的原字符串左边界、右边界的下标，再各自向两边扩散比较\n",
    "    dp[i]定义为原字符串的前i个字符形成的子串中满足长度至少为k的不重叠回文串的最大个数\n",
    "    按照贪心的思想，要使得个数最多，那么每个回文串的长度要满足大于等于k且最小，这样才能容纳更多的回文串。我们\n",
    "    按照中心扩散的思想，枚举中心点，再计算出假设的回文中心点对应原字符串s中的左右字符下标，进行扩散比较，如果\n",
    "    是回文且满足长度大于等于k了，就可以终止本轮扩散了\n",
    "    由于我们枚举的是中心点，而dp的定义实际上是右边界的定义，所以dp[right] = dp[left] + 1（这里暂不考虑边界的各种偏移）\n",
    "    '''\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        '''\n",
    "        左边多加一个初始值，是因为对于dp[i]来说，初始值实际上先要从dp[i - 1]获得，如果i从0开始，就要多一层i - 1 >= 0的\n",
    "        判断了\n",
    "        '''\n",
    "        dp = [0] * (n + 1)\n",
    "        '''\n",
    "        枚举扩展字符串a_b_a的中心点\n",
    "        '''\n",
    "        for i in range(2 * n - 1):\n",
    "            '''\n",
    "            计算出中心点对应的原始字符串中左右起点的下标\n",
    "            '''\n",
    "            left, right = i // 2, (i + 1) // 2\n",
    "            '''\n",
    "            初始值来自于前一个，还要和dp[left + 1]比较是因为，存在两个中心点对应\n",
    "            一个原始下标，在计算第二个中心点的逻辑时，第一个中心点计算出来的结果可能\n",
    "            已经在dp[left + 1]中了，所以还要和自己比一下\n",
    "            '''\n",
    "            dp[left + 1] = max(dp[left + 1], dp[left])\n",
    "            '''\n",
    "            扩散比较，只要发现回文串长度大于等于k就可以停止了\n",
    "            '''\n",
    "            while left >= 0 and right < n and s[left] == s[right]:\n",
    "                if right - left + 1 >= k:\n",
    "                    '''\n",
    "                    dp要比原始s的下标多一，所以是right + 1，同样的dp[left]也不包括原始字符串\n",
    "                    下标left，因为原始字符串left下标是在当前的回文子串中\n",
    "                    这里和平常的dp递推不太一样，平时都是求dp[i]用dp[i - 1]递推得来，而这里是\n",
    "                    遍历i，递推出未来i + j的值，后续要习惯这种思路\n",
    "                    '''\n",
    "                    dp[right + 1] = max(dp[right + 1], dp[left] + 1)\n",
    "                    break\n",
    "                left -= 1\n",
    "                right += 1\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(2 * n - 1):\n",
    "            l = i // 2\n",
    "            r = i // 2 + (i & 1)\n",
    "            f[l + 1] = max(f[l + 1], f[l])\n",
    "            while l >= 0 and r < n and s[l] == s[r]:\n",
    "                if r - l + 1 >= k:\n",
    "                    f[r + 1] = f[l] + 1\n",
    "                    break\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if k==1:\n",
    "            return n \n",
    "\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(2*n-1):\n",
    "            left, right = i//2, i//2+(i%2)\n",
    "            dp[left+1] = max(dp[left+1], dp[left])\n",
    "            while left>=0 and right<n and s[left]==s[right]:\n",
    "                if right-left+1>=k:\n",
    "                    dp[right+1] = max(dp[right+1],dp[left]+1)\n",
    "                    break \n",
    "                left -= 1\n",
    "                right += 1\n",
    "                \n",
    "                \n",
    "            \n",
    "        #print(dp[3])\n",
    "        return dp[n]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        for i in range(2 * n - 1):\n",
    "            left, right = i // 2, (i + 1) // 2\n",
    "            dp[left + 1] = max(dp[left + 1], dp[left])\n",
    "            while left >= 0 and right < n and s[left] == s[right]:\n",
    "                if right - left + 1 >= k:\n",
    "                    dp[right + 1] = max(dp[right + 1], dp[left] + 1)\n",
    "                    break\n",
    "                left -= 1\n",
    "                right += 1\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if k==1:\n",
    "            return n \n",
    "\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            if i-k<0:\n",
    "                continue \n",
    "            dp[i] = dp[i-1]\n",
    "            for j in range(i-k+1,0,-1):\n",
    "                if s[j-1:i]==s[j-1:i][::-1]:\n",
    "                    dp[i] = max(dp[i],1+dp[j-1])\n",
    "                    break\n",
    "        #print(dp[3])\n",
    "        return dp[n]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        f=[0]*(n+1)\n",
    "        for i in range(2*n-1):\n",
    "            l,r=i//2,i//2+i%2\n",
    "            f[l+1]=max(f[l+1],f[l])\n",
    "            while l>=0 and r<n and s[l]==s[r]:\n",
    "                if r-l+1>=k:\n",
    "                    f[r+1]=max(f[r+1],f[l]+1)\n",
    "                    break\n",
    "                l-=1\n",
    "                r+=1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(2 * n - 1):\n",
    "            l, r = i // 2, i // 2 + i % 2  # 中心扩展法\n",
    "            f[l + 1] = max(f[l + 1], f[l])\n",
    "            while l >= 0 and r < n and s[l] == s[r]:\n",
    "                if r - l + 1 >= k:\n",
    "                    f[r + 1] = max(f[r + 1], f[l] + 1)\n",
    "                    break\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        m = len(s)\n",
    "        first_index = [-1] * m\n",
    "        for i in range(m):\n",
    "            for j in range(i, -1, -1):\n",
    "                if i - j + 1 >= k and s[j: i+1] == s[j: i+1][::-1]:\n",
    "                    first_index[i] = j\n",
    "                    break\n",
    "        res = [0] * m\n",
    "        for i in range(m):\n",
    "            if i == 0 and first_index[i] == 0:\n",
    "                res[i] = 1\n",
    "            elif first_index[i] == 0:\n",
    "                res[i] = max(res[i-1], 1)\n",
    "            elif first_index[i] > 0:\n",
    "                res[i] = max(res[i-1], res[first_index[i]-1] + 1)\n",
    "            else:\n",
    "                res[i] = res[i-1]\n",
    "        return res[-1]\n",
    "            \n",
    "             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        \n",
    "        # def cherck_str(ss):\n",
    "        #     l, r = 0, len(ss)-1\n",
    "        #     while l <= r:\n",
    "        #         if ss[l] == ss[r]:\n",
    "        #             l+=1\n",
    "        #             r-=1\n",
    "        #         else:\n",
    "        #             break\n",
    "        #     return l > r\n",
    "        # if k == len(s):\n",
    "        #     return int(cherck_str(s))\n",
    "        # li = []\n",
    "        # for i in range(len(s)-k):\n",
    "        #     if cherck_str(s[i:i+k]):\n",
    "        #         li.append([i,i+k-1])\n",
    "        #     if cherck_str(s[i:i+k+1]):\n",
    "        #         li.append([i,i+k])\n",
    "        #     if i == len(s)-k-1 and cherck_str(s[i+1:]):\n",
    "        #         li.append([i+1,i+k])\n",
    "        # if len(li) == 0:\n",
    "        #     return 0\n",
    "        # dp = [0]*len(li)\n",
    "        # dp[0] = 1\n",
    "        # for i in range(1,len(li)):\n",
    "        #     j = i - 1\n",
    "        #     while j >= 0 and li[j][1] >= li[i][0]:\n",
    "        #         j-=1\n",
    "        #     if j == -1:\n",
    "        #         dp[i] = max(1,dp[i-1])\n",
    "        #     else:\n",
    "        #         dp[i] = max(dp[j]+1,dp[i-1])\n",
    "        # return dp[-1]\n",
    "        n = len(s)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(2 * n - 1):\n",
    "            l, r = i // 2, i // 2 + i % 2  # 中心扩展法\n",
    "            f[l + 1] = max(f[l + 1], f[l])\n",
    "            while l >= 0 and r < n and s[l] == s[r]:\n",
    "                if r - l + 1 >= k:\n",
    "                    f[r + 1] = max(f[r + 1], f[l] + 1)\n",
    "                    break\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        return f[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        # 初始化d数组，用于存储每个位置的最优解\n",
    "        d = [0 for _ in range(n + 1)]\n",
    "\n",
    "        # 辅助函数，用于检查子串是否是回文\n",
    "        def ck(ss):\n",
    "            j = len(ss) - 1\n",
    "            i = 0\n",
    "            while i < j:\n",
    "                if ss[i] == ss[j]:\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # 遍历每个可能的子串\n",
    "        for i in range(k, n + 1):\n",
    "            tt = 0\n",
    "            # 遍历所有可能的长度为k的子串，检查其是否是回文\n",
    "            for l in range(k, i + 1):\n",
    "                t = s[i - l:i]\n",
    "                if ck(t):\n",
    "                    d[i] = 1\n",
    "                    tt = max(tt, d[i - l])\n",
    "                    # 一旦找到一个回文串，就中断内层循环\n",
    "                    break\n",
    "            \n",
    "            # 更新d数组的当前位置的值\n",
    "            d[i] = max(d[i - 1], d[i] + tt)\n",
    "                \n",
    "        return d[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        if k==1: return len(s)\n",
    "        res = []\n",
    "        for i in range(len(s)-k+1):\n",
    "            for j in range(i+k, len(s)+1):\n",
    "                x, n = s[i:j], j-i\n",
    "                if x[:n//2] == x[::-1][:n//2]: \n",
    "                    res.append((i, j-1))\n",
    "                    break\n",
    "        res.sort(key = lambda x: x[1])\n",
    "        if not res: return 0\n",
    "        tmp_max, x = res[0][1], 1\n",
    "        for s, e in res[1:]:\n",
    "            if s>tmp_max: \n",
    "                tmp_max = e\n",
    "                x += 1\n",
    "\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if k == 1:\n",
    "            return n\n",
    "        z = 31\n",
    "        h = [0] * n\n",
    "        a = [0] * n\n",
    "        b = [0] * n\n",
    "        h[0] = 1\n",
    "        a[0] = ord(s[0]) - 96\n",
    "        b[-1] = ord(s[-1]) - 96\n",
    "        mod = int(1e9 + 7)\n",
    "        for i in range(1,n):\n",
    "            h[i] = (h[i-1] * z) % mod\n",
    "            a[i] = (a[i-1] * z + ord(s[i]) - 96) % mod\n",
    "            b[n-i-1] = (b[n-i] * z + ord(s[n-i-1]) - 96) % mod\n",
    "        def get_hash(l:int,r:int)->int:\n",
    "            if l == 0:\n",
    "                return a[r]\n",
    "            return (mod + a[r] - (a[l-1] * h[r - l + 1]) % mod) % mod\n",
    "        def get_hash_1(l:int,r:int)->int:\n",
    "            if r == n-1:\n",
    "                return b[l]\n",
    "            return (mod + b[l] - (b[r+1] * h[r - l + 1]) % mod) % mod\n",
    "        dp = [0] * n\n",
    "        for i in range(k-1,n):\n",
    "            dp[i] = dp[i-1]\n",
    "            for j in range(i-k,-2,-1):\n",
    "                if j < 0:\n",
    "                    if get_hash(j+1,(j+1+i)//2) == get_hash_1((j+1+i+1)//2,i):\n",
    "                        dp[i] = max(dp[i], 1)\n",
    "                else:\n",
    "                    if get_hash(j+1,(j+1+i)//2) == get_hash_1((j+1+i+1)//2,i):\n",
    "                        dp[i] = max(dp[i], dp[j]+1)\n",
    "                        break\n",
    "        return dp[n-1]\n",
    "        \n",
    "s = Solution()\n",
    "s.maxPalindromes(\"abaccdbbd\",3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        class Node:\n",
    "            def __init__(self, c, start, size):\n",
    "                self.c = c\n",
    "                self.start = start\n",
    "                self.size = size\n",
    "                self.next = self.prev = None\n",
    "        head = last = Node('', -1, -1)\n",
    "        byC = defaultdict(list)\n",
    "        states = [0]*(len(s)+1)\n",
    "        for i, c in enumerate(s):\n",
    "            if c == last.c:\n",
    "                last.size += 1\n",
    "            else:\n",
    "                last.next = node = Node(c, i, 1)\n",
    "                node.prev = last\n",
    "                last = node\n",
    "                byC[c].append(node)\n",
    "            states[i+1] = states[i] \n",
    "            if last.size >= k:\n",
    "                for l in range(k, last.size+1):\n",
    "                    states[i+1] = max(states[i+1], states[i-l+1]+1)\n",
    "            for node in byC[c][-2::-1]:\n",
    "                if node.size < last.size or i-(node.start+node.size-last.size-1) < k: continue\n",
    "                node1, temp = node.next, last.prev\n",
    "                while node1.start < temp.start:\n",
    "                    if node1.c != temp.c or node1.size != temp.size: break\n",
    "                    node1, temp = node1.next, temp.prev\n",
    "                else:\n",
    "                    states[i+1] = max(states[i+1], states[node.start+node.size-last.size]+1)\n",
    "        return states[-1]\n",
    "\n",
    "                    \n",
    "        \n",
    "\n",
    "        # S[N] = max(S[N-1], S[x]+1 s[x+1:N])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        a = {}\n",
    "        n = len(s)\n",
    "        def f(x, y):\n",
    "            d = 0\n",
    "            while ((x - d)>=0) and ((y + d)<n):\n",
    "                if s[x - d]==s[y + d]:\n",
    "                    if (y + d - x + d + 1)>=k:\n",
    "                        if (x - d) in a:\n",
    "                            a[x -d] = min(a[x -d], y + d) \n",
    "                        else:\n",
    "                            a[x -d] = y + d \n",
    "                        return \n",
    "                else:\n",
    "                    return \n",
    "                d += 1 \n",
    "        for j in range(n):\n",
    "            f(j, j)\n",
    "            if j<(n - 1):\n",
    "                f(j, j+1)\n",
    "        @cache \n",
    "        def g(j):\n",
    "            if j==n:\n",
    "                return 0\n",
    "            b = g(j + 1)\n",
    "            if j in a:\n",
    "                b = max(b, 1 + g(1 + a[j]))\n",
    "            return b\n",
    "        return g(0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            if i+1<n:\n",
    "                dp[i][i+1] = 1 if s[i] == s[i+1] else 0\n",
    "            for j in range(i+2, n):\n",
    "                if s[i] == s[j] and dp[i+1][j-1]:\n",
    "                    dp[i][j] = 1\n",
    "\n",
    "        ans = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            ans[i+1] = ans[i]\n",
    "            for j in range(i-k+1, -1, -1):\n",
    "                if dp[j][i] and ans[j]+1>ans[i+1]:\n",
    "                    ans[i+1] = ans[j] + 1\n",
    "        return ans[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        # we can use a O(n^2) time complexity to calculate all s[i:j] (which is included both side )is a palindrome\n",
    "        # let f[i] represent the maximum number of non-overlapping palindrome substrings of s[0:i]，we don't care how\n",
    "        # to split the substring in s[0:i]\n",
    "        # than we enumerate\n",
    "        n = len(s)\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        # calculate all s[i:j] is a palindrome\n",
    "        for d in range(1, n + 1):\n",
    "            for i in range(n):\n",
    "                j = i + d - 1\n",
    "                if j >= n: break\n",
    "                dp[i][j] = s[i] == s[j] and (d <= 2 or dp[i + 1][j - 1]) \n",
    "        #print(f'dp:{dp},k:{k}')\n",
    "        f = [0] * n\n",
    "        for i in range(n):\n",
    "            f[i] = max(f[i], f[i - 1] if i > 0 else 0)\n",
    "            l = i\n",
    "            for add in range(2):\n",
    "                r = l + k - 1 + add\n",
    "                #print(f'l:{l},r:{r},f:{f}')\n",
    "                if r < n and dp[l][r]:\n",
    "                    # print(f'r:{r},f:{f}')\n",
    "                    f[r] = max(f[r], (f[l - 1] if l > 0 else 0) + 1)\n",
    "            #print(f'i:{i},f:{f}')\n",
    "        return f[n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f = [[False] * n for _ in range(n)]\n",
    "\n",
    "        def ispalindrom(l, r):\n",
    "            while l >= 0 and r < n and s[l] == s[r]:\n",
    "                f[l][r] = True\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            ispalindrom(i, i)\n",
    "            ispalindrom(i, i + 1)\n",
    "\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1]\n",
    "            for j in range(1, i + 1):\n",
    "                if i - j + 1 >= k and f[j - 1][i - 1]:\n",
    "                    dp[i] = max(dp[i], dp[j - 1] + 1)\n",
    "        # print(dp)\n",
    "        return dp[-1]\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f = [[False] * n for _ in range(n)]\n",
    "\n",
    "        def ispalindrom(l, r):\n",
    "            while l >= 0 and r < n and s[l] == s[r]:\n",
    "                f[l][r] = True\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            ispalindrom(i, i)\n",
    "            ispalindrom(i, i + 1)\n",
    "\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            dp[i] = dp[i - 1]\n",
    "            for j in range(i + 1):\n",
    "                if i - j + 1 >= k and f[j][i]:\n",
    "                    dp[i] = max(dp[i], dp[j - 1] + 1 if j - 1 >= 0 else 1)\n",
    "        # print(dp)\n",
    "        return dp[-1]\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        is_palin = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(2):\n",
    "                l = i\n",
    "                r = i + j\n",
    "                while l >= 0 and r < n and s[l] == s[r]:\n",
    "                    is_palin[l][r] = 1\n",
    "                    l -= 1\n",
    "                    r += 1\n",
    "        # @lru_cache(None)\n",
    "        # def dfs(st):\n",
    "        #     if n - st < k:\n",
    "        #         return 0\n",
    "        #     ans = 0\n",
    "        #     for i in range(st + 1, n + 1):\n",
    "        #         ans = max(ans, dfs(i) + int(i-1 - st + 1 >= k and is_palin[st][i-1]))\n",
    "        #     return ans\n",
    "        # return dfs(0)\n",
    "        dp = [0] * (n + 1) # (0,i-1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i-1]\n",
    "            for st in range(i):\n",
    "                if i - st >= k and is_palin[st][i-1]:\n",
    "                    dp[i] = max(dp[i], dp[st] + 1)\n",
    "        return dp[-1]\n",
    "\n",
    "    def maxPalindromes1(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0] * n\n",
    "        for i in range(len(s)):\n",
    "            dp[i] = max(dp[i], dp[i-1])\n",
    "            for j in range(2):\n",
    "                l = i\n",
    "                r = i + j\n",
    "                while l >= 0 and r < n and s[l] == s[r]:\n",
    "                    if r - l + 1 >= k:\n",
    "                        dp[r] = max(dp[r], dp[l-1] + 1)\n",
    "                        break\n",
    "                    l -= 1\n",
    "                    r += 1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        #copy\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        res = 0\n",
    "        pre = n\n",
    "        for  i in range(n-1,-1,-1):\n",
    "            maxcnt = 0\n",
    "            for j in range(i,pre):\n",
    "                if s[i] == s[j]:\n",
    "                    if j -i <= 1:\n",
    "                        dp[i][j] = j-i+1\n",
    "                    elif dp[i+1][j-1]:\n",
    "                        dp[i][j] = dp[i+1][j-1] + 2\n",
    "                maxcnt = max(maxcnt,dp[i][j])\n",
    "            if maxcnt >= k:\n",
    "                res +=1\n",
    "                pre = i \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            l = i\n",
    "            r = i\n",
    "            while l >= 0 and r < n:\n",
    "                if s[l] == s[r]:\n",
    "                    dp[l][r] = True\n",
    "                else:\n",
    "                    break\n",
    "                l -= 1\n",
    "                r += 1\n",
    "                    \n",
    "        for i in range(n):\n",
    "            l = i\n",
    "            r = i + 1\n",
    "            while l >= 0 and r < n:\n",
    "                if s[l] == s[r]:\n",
    "                    dp[l][r] = True\n",
    "                else:\n",
    "                    break\n",
    "                l -= 1\n",
    "                r += 1\n",
    "                \n",
    "        res = 0\n",
    "        # print(dp)\n",
    "        cnt = [0 for _ in range(n)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i > 0:\n",
    "                cnt[i] = cnt[i - 1]\n",
    "            for j in range(i - k + 2):\n",
    "                if dp[j][i]:\n",
    "                    # print(j, i, cnt, cnt[j - 1])\n",
    "                    cnt[i] = max(cnt[i], (cnt[j - 1] if j > 0 else 0) + 1)\n",
    "        # print(cnt)\n",
    "        return cnt[n - 1]\n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        check = [[0] * n for _ in range(n)]\n",
    "        # [i+1, j-1] -> [i, j]\n",
    "        for i in range(n, -1, -1):\n",
    "            for j in range(i, n):\n",
    "                if j - i <= 1 and s[i] == s[j]:\n",
    "                    check[i][j] = 1\n",
    "                elif s[i] == s[j] and check[i + 1][j - 1] == 1:\n",
    "                    check[i][j] = 1\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1]\n",
    "            for j in range(0, i - k + 1):\n",
    "                dp[i] = max(dp[i], dp[j] + check[j][i - 1])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f = [[False] * n for _ in range(n)]\n",
    "\n",
    "        def ispalindrom(l, r):\n",
    "            while l >= 0 and r < n and s[l] == s[r]:\n",
    "                f[l][r] = True\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            ispalindrom(i, i)\n",
    "            ispalindrom(i, i + 1)\n",
    "\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            dp[i] = dp[i - 1]\n",
    "            for j in range(i + 1):\n",
    "                if i - j + 1 >= k and f[j][i]:\n",
    "                    dp[i] = max(dp[i], (dp[j - 1] + 1) if j - 1 >= 0 else 1)\n",
    "        # print(dp)\n",
    "        return dp[-1]\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[False]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = True\n",
    "\n",
    "        for j in range(1, n):\n",
    "            for i in range(j):\n",
    "                if s[i] == s[j] and (j-i==1 or dp[i+1][j-1]):\n",
    "                    dp[i][j] = True\n",
    "\n",
    "        # f[i]: [0...i-1]不重叠最大数目\n",
    "        f = [0 for _ in range(n+1)]\n",
    "        for j in range(1, n+1):\n",
    "            f[j] = f[j-1]\n",
    "            for i in range(j-k, -1, -1):\n",
    "                if dp[i][j-1]:\n",
    "                    f[j] = max(f[j], 1+f[i])\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[False]*n for _ in range(n)]\n",
    "\n",
    "        for i in range(n,-1,-1):\n",
    "            for j in range(i,n):\n",
    "                if s[i] == s[j] and (j-i<=1 or dp[i+1][j-1]):\n",
    "                    dp[i][j] = True\n",
    "\n",
    "        f = [0]*(n+1)\n",
    "        for i in range(k,n+1):\n",
    "            f[i] = max(f[i],f[i-1])\n",
    "            for x in range(i-k+1):\n",
    "                if dp[x][i-1]:\n",
    "                    f[i] = max(f[i],f[x]+1)\n",
    "\n",
    "\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n, ans = len(s), 0\n",
    "        \n",
    "        dp = [0 for i in range(n)]\n",
    "        isP = [[True for i in range(n)] for j in range(n)]\n",
    "        \n",
    "       \n",
    "        \n",
    "        \n",
    "        for j in range(1, n):\n",
    "            for i in range(n):\n",
    "                if i + j < n:\n",
    "                    isP[i][i+j] = (s[i] == s[i+j] and isP[i+1][i+j-1])\n",
    "        \n",
    "        #print(isP)\n",
    "            \n",
    "        \n",
    "        for i in range(n):\n",
    "            if i >= 1:\n",
    "                dp[i] = max(dp[i], dp[i-1])\n",
    "            else:\n",
    "                dp[i] = 1 if k == 1 else 0\n",
    "            for j in range(i, -1, -1):\n",
    "                if isP[j][i] and i - j + 1 >= k:\n",
    "                    if j >= 1:\n",
    "                        dp[i] = max(dp[i], dp[j-1] + 1)\n",
    "                    else:\n",
    "                        dp[i] = max(dp[i], 1)\n",
    "                    break\n",
    "            ans = max(ans, dp[i])\n",
    "        \n",
    "       \n",
    "        \n",
    "        #print (dp)\n",
    "                    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        is_pali = [[False for i in range(n)] for j in range(n)]\n",
    "        is_pali[n-1][n-1] = True\n",
    "        for i in range(0, n-1):\n",
    "            is_pali[i][i] = True\n",
    "            is_pali[i][i+1] = s[i] == s[i+1]\n",
    "\n",
    "        for length in range(2, n):\n",
    "            for i in range(0, n-length):\n",
    "                is_pali[i][i+length] = is_pali[i+1][i+length-1] and (s[i] == s[i+length])\n",
    "        \n",
    "        dp = [0 for i in range(n+1)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i] = dp[i+1]\n",
    "            for j in range(i, n):\n",
    "                if is_pali[i][j] and (j-i)+1 >= k:\n",
    "                    # print(i, j)\n",
    "                    dp[i] = max(dp[i], 1+dp[j+1])\n",
    "        \n",
    "        return dp[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[False for _ in range(n)]for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i]=True\n",
    "            if i!=0:\n",
    "                if s[i-1]==s[i]:\n",
    "                    dp[i-1][i]=True\n",
    "        for i in range(n-3,-1,-1):\n",
    "            for j in range(i+2,n):\n",
    "                if s[i]==s[j] and dp[i+1][j-1]:\n",
    "                    dp[i][j]=True\n",
    "        #print(dp)\n",
    "        ans=0\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if i+k-1<n and dp[i][i+k-1]:\n",
    "                ans+=1\n",
    "                i+=k\n",
    "                continue\n",
    "            if i+k<n and dp[i][i+k]:\n",
    "                ans+=1\n",
    "                i+=k+1\n",
    "                continue\n",
    "            i+=1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for end in range(n):\n",
    "            for start in range(end+1):\n",
    "                if end <= start + 1:\n",
    "                    dp[start][end] = end-start+1 if s[start] == s[end] else 0\n",
    "                else:\n",
    "                    if s[start] == s[end] and dp[start+1][end-1]:\n",
    "                        dp[start][end] = dp[start+1][end-1]+2\n",
    "        fun = [0]*(n+1)\n",
    "        for now in range(n-1, -1, -1):\n",
    "            fun[now] = fun[now+1]\n",
    "            for nex in range(now, n):\n",
    "                if dp[now][nex] >= k:\n",
    "                    fun[now] = max(fun[now], 1+fun[nex+1])\n",
    "        return fun[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ManacherPlindrome:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def max(a, b):\n",
    "        return a if a > b else b\n",
    "\n",
    "    @staticmethod\n",
    "    def manacher(s):\n",
    "        # 马拉车算法\n",
    "        n = len(s)\n",
    "        arm = [0] * n\n",
    "        left, right = 0, -1\n",
    "        for i in range(0, n):\n",
    "            a, b = arm[left + right - i], right - i + 1\n",
    "            a = a if a < b else b\n",
    "            k = 1 if i > right else a\n",
    "\n",
    "            # 持续增加回文串的长度\n",
    "            while 0 <= i - k and i + k < n and s[i - k] == s[i + k]:\n",
    "                k += 1\n",
    "            arm[i] = k\n",
    "\n",
    "            # 更新右侧最远的回文串边界\n",
    "            k -= 1\n",
    "            if i + k > right:\n",
    "                left = i - k\n",
    "                right = i + k\n",
    "        # 返回每个位置往右的臂长其中 s[i-arm[i]+1: i+arm[i]] 为回文子串范围\n",
    "        # 即以i为中心的最长回文子串长度\n",
    "        return arm\n",
    "\n",
    "    def palindrome(self, s: str) -> (list, list):\n",
    "        # 获取区间的回文串信息\n",
    "        n = len(s)\n",
    "        # 保证所有的回文串为奇数长度，且中心为 # 的为原偶数回文子串，中心为 字母 的为原奇数回文子串\n",
    "        t = \"#\" + \"#\".join(list(s)) + \"#\"\n",
    "        dp = self.manacher(t)\n",
    "        m = len(t)\n",
    "\n",
    "        # 以当前索引作为边界开头的回文子串结束位置索引\n",
    "        start = [[] for _ in range(n)]\n",
    "        # 以当前索引作为边界结尾的回文子串起始位置索引\n",
    "        end = [[] for _ in range(n)]\n",
    "\n",
    "        for j in range(m):\n",
    "            left = j - dp[j] + 1\n",
    "            right = j + dp[j] - 1\n",
    "            while left <= right:\n",
    "                if t[left] != \"#\":\n",
    "                    start[left // 2].append(right // 2)\n",
    "                    end[right // 2].append(left // 2)\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        return start, end\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        _, end = ManacherPlindrome().palindrome(s)\n",
    "\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            dp[i + 1] = dp[i]\n",
    "            for j in end[i]:\n",
    "                if i - j + 1 >= k and dp[j] + 1 > dp[i + 1]:\n",
    "                    dp[i + 1] = dp[j] + 1\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        # we can use a O(n^2) time complexity to calculate all s[i:j] (which is included both side )is a palindrome\n",
    "        # let f[i] represent the maximum number of non-overlapping palindrome substrings of s[0:i]，we don't care how\n",
    "        # to split the substring in s[0:i]\n",
    "        # than we enumerate\n",
    "        n = len(s)\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        # calculate all s[i:j] is a palindrome\n",
    "        for d in range(1, n + 1):\n",
    "            for i in range(n):\n",
    "                j = i + d - 1\n",
    "                if j >= n: break\n",
    "                dp[i][j] = s[i] == s[j] and (d <= 2 or dp[i + 1][j - 1])\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            re = dfs(i - 1)\n",
    "            for add in range(2):\n",
    "                l = i - k + 1 - add\n",
    "                if l >= 0 and dp[l][i]:\n",
    "                    re = max(re, 1 + dfs(l - 1))\n",
    "            return re\n",
    "        return dfs(n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        # def check(i, j):\n",
    "        #     while i < j and s[i] == s[j]:\n",
    "        #         i += 1\n",
    "        #         j -= 1\n",
    "        #     return i >= j\n",
    "\n",
    "        f = [[False] * (n + 1) for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(n):\n",
    "                st, en = j, j + i - 1\n",
    "                if en >= n:\n",
    "                    break\n",
    "                if i == 1:\n",
    "                    f[st][en] = True\n",
    "                elif i == 2:\n",
    "                    f[st][en] = s[st] == s[en]\n",
    "                else:\n",
    "                    f[st][en] = f[st + 1][en - 1] & (s[st] == s[en])\n",
    "\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            \n",
    "            t = 0\n",
    "            # 不选！\n",
    "            t = max(t, dfs(i + 1))\n",
    "\n",
    "            for j in range(i + k - 1, n):\n",
    "                # 选\n",
    "                if f[i][j]:\n",
    "                    t = max(t, dfs(j + 1) + 1)\n",
    "            return t\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        is_palin = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(2):\n",
    "                l = i\n",
    "                r = i + j\n",
    "                while l >= 0 and r < n and s[l] == s[r]:\n",
    "                    is_palin[l][r] = 1\n",
    "                    l -= 1\n",
    "                    r += 1\n",
    "        @lru_cache(None)\n",
    "        def dfs(st):\n",
    "            if n - st < k:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for i in range(st + 1, n + 1):\n",
    "                ans = max(ans, dfs(i) + int(i-1 - st + 1 >= k and is_palin[st][i-1]))\n",
    "            return ans\n",
    "        return dfs(0)\n",
    "\n",
    "    def maxPalindromes1(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0] * n\n",
    "        for i in range(len(s)):\n",
    "            dp[i] = max(dp[i], dp[i-1])\n",
    "            for j in range(2):\n",
    "                l = i\n",
    "                r = i + j\n",
    "                while l >= 0 and r < n and s[l] == s[r]:\n",
    "                    if r - l + 1 >= k:\n",
    "                        dp[r] = max(dp[r], dp[l-1] + 1)\n",
    "                        break\n",
    "                    l -= 1\n",
    "                    r += 1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def maxPalindromes(self, s, k):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        news = \"#\"\n",
    "        for i in range(n):\n",
    "           news += s[i] + \"#\"\n",
    "        ##0 -> 1\n",
    "        ##1 -> 3\n",
    "        pre = [[False for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(len(news)):\n",
    "            j = 0\n",
    "            while i - j >= 0 and i + j < len(news) and news[i - j] == news[i + j]:\n",
    "                if news[i] == \"#\":\n",
    "                  if j % 2 == 1:\n",
    "                    pre[(i - j - 1)//2][(i + j - 1)//2] = True\n",
    "                else:\n",
    "                  if j % 2 == 0:\n",
    "                    pre[(i - j - 1) // 2][(i + j - 1) // 2] = True\n",
    "                j += 1\n",
    "\n",
    "\n",
    "\n",
    "        #### interval dp\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if n - i + 1 < k:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for l in range(i, n):\n",
    "                if pre[i][l] and l - i + 1 >=k:\n",
    "                    ans = max(ans, 1 + dfs(l + 1))\n",
    "            ans = max(ans,dfs(i + 1))\n",
    "\n",
    "            return ans\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        d = defaultdict(set)\n",
    "        def judge(idx: int):\n",
    "            l, r = idx, idx\n",
    "            while l >= 0 and r < len(s) and s[l] == s[r]:\n",
    "                if r - l + 1 >= k:\n",
    "                    d[r].add(l)\n",
    "                l, r = l - 1, r + 1\n",
    "            l, r = idx - 1, idx\n",
    "            while l >= 0 and r < len(s) and s[l] == s[r]:\n",
    "                if r - l + 1 >= k:\n",
    "                    d[r].add(l)\n",
    "                l, r = l - 1, r + 1\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            judge(i)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1]\n",
    "            for j in d[i - 1]:\n",
    "                dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        d = defaultdict(set)\n",
    "        def judge(idx: int):\n",
    "            l, r = idx, idx\n",
    "            while l >= 0 and r < len(s) and s[l] == s[r]:\n",
    "                if r - l + 1 >= k:\n",
    "                    d[r].add(l)\n",
    "                l, r = l - 1, r + 1\n",
    "            l, r = idx - 1, idx\n",
    "            while l >= 0 and r < len(s) and s[l] == s[r]:\n",
    "                if r - l + 1 >= k:\n",
    "                    d[r].add(l)\n",
    "                l, r = l - 1, r + 1\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            judge(i)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1]\n",
    "            for j in range(i, -1, -1):\n",
    "                if j in d[i - 1]:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPalindromes(self, s: str, k: int) -> int:\n",
    "        L=[]\n",
    "        for i in range(len(s)):\n",
    "            flag=True\n",
    "            for j in range(len(s)//2+1):\n",
    "                if i+j>=len(s) or i-j<0 or s[i+j]!=s[i-j]:\n",
    "                    flag=False\n",
    "                    break\n",
    "                if 2*j+1>=k and flag:\n",
    "                    L.append((i-j,i+j))\n",
    "        for i in range(len(s)):\n",
    "            flag=True\n",
    "            for j in range(1,len(s)//2+1):\n",
    "                if i+j>=len(s) or i-j+1<0 or s[i+j]!=s[i-j+1]:\n",
    "                    flag=False\n",
    "                    break\n",
    "                if 2*j>=k and flag:\n",
    "                    L.append((i-j+1,i+j))\n",
    "        dic=dict()\n",
    "        for i in L:\n",
    "            dic[i[1]]=min(dic.get(i[1],i[1]+1),i[1]-i[0]+1)\n",
    "        dp=[0]*(len(s)+1)\n",
    "        for i in range(1,len(dp)):\n",
    "            if i-1 in dic:\n",
    "                dp[i]=max(dp[i-1],dp[i-dic[i-1]]+1)\n",
    "            else:\n",
    "                dp[i]=dp[i-1]\n",
    "        return dp[-1]\n",
    "                    \n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
